#define _CRT_SECURE_NO_WARNINGS 1
vector<vector<string>> ans;
vector<string> res;
class Solution {
public:

    void dfs(string& s, int pos, int n, vector<vector<bool>>& dp) {
        if (pos == n) {
            ans.push_back(res);
            return;
        }
        for (int i = pos; i < n; i++) {
            if (dp[pos][i]) {
                res.push_back(s.substr(pos, i - pos + 1));
                dfs(s, i + 1, n, dp);
                res.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        res.clear();
        ans.clear();
        int len = s.size();
        vector<vector<bool>>dp(len + 1, vector<bool>(len + 1, true));
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (i == j)dp[i][j] = true;
            }
        }
        for (int i = 1; i <= len; i++) {
            for (int l = 0; l + i - 1 < len; l++) {
                int r = l + i - 1;
                if (i == 1)continue;
                if (s[l] == s[r]) {
                    dp[l][r] = dp[l + 1][r - 1];
                }
                else {
                    dp[l][r] = false;
                }
            }
        }

        dfs(s, 0, len, dp);
        return ans;
    }
};